//
//  Train. 快速排序.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/4.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class SolutionQuickSort<E:Comparable> {
    func quickSort(a: inout [E]) {
        quickPart(a: &a, start: 0, end: a.count - 1)
    }
    func quickPart(a: inout [E], start: Int, end: Int) {
        if end <= start {
            return
        }
        let mid = partion(a: &a, start, end: end)
        quickPart(a: &a, start: start, end: mid - 1)
        quickPart(a: &a, start: mid + 1, end: end)
    }
    // 将一个区间分割成两段，并返回中间的index
    // 其中一种简单的方法：找出小于pivot的个数。
    func partion(a: inout [E], _ start: Int , end: Int) -> Int{
        let pivot = end
        var counter = start
        for i in start..<end {
            // 如果当前的值小于基准值。就将a[i]的元素放到a[counter]里
            if a[i] < a[pivot] {
               let temp = a[counter]
                a[counter] = a[i]
                a[i] = temp
                counter += 1
            }
        }
        // 最后将a[pivot]的值与a[counter]位置交换
        let tmp = a[pivot]
        a[pivot] = a[counter]
        a[counter] = tmp
        return counter
    }
}


class SolutionQuickSortTrain {
    static func test() {
        var array = [1, 11, 8, 2, 11, 4, 1, 5 , 7, 10, 3]
        let solution = SolutionQuickSort<Int>()
        solution.quickSort(a: &array)
        print(array)
    }
}
